SherbyNet - /page/wikibook/entry.mu

<!DOCTYPE html>

<title>Graph bandwidth</title>

</head>

Graph bandwidth

</h1>

</header>

In <a href="Graph_theory" title="Graph theory">graph theory</a>, the graph bandwidth problem is to label the n <a href="Vertex_(graph_theory)" title="Vertex (graph theory)">vertices</a> vi of a <a href="Graph_(discrete_mathematics)" title="Graph (discrete mathematics)">graph</a> G with distinct <a href="Integer" title="Integer">integers</a> ⁠<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(v_{i})}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(v_{i})}</annotation>

</semantics>

</math><img src="./e5cf38504f2236c57a413fa518cf503da8269672.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.015ex; height:2.843ex;" alt="{\displaystyle f(v_{i})}" loading="lazy">⁠ so that the quantity <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \max\{\,|f(v_{i})-f(v_{j})|:v_{i}v_{j}\in E\,\}}">

</mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \max\{\,|f(v_{i})-f(v_{j})|:v_{i}v_{j}\in E\,\}}</annotation>

</semantics>

</math><img src="./29926bd327a726437d70d825e236ef07f03b60ed.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:32.217ex; height:3.009ex;" alt="{\displaystyle \max\{\,|f(v_{i})-f(v_{j})|:v_{i}v_{j}\in E\,\}}" loading="lazy"> is minimized (E is the edge set of G).<a href="#cite_note-1">[1]</a>

The problem may be visualized as placing the vertices of a graph at distinct integer points along the x-axis so that the length of the longest edge is minimized. Such placement is called linear graph arrangement, linear graph layout or linear graph placement.<a href="#cite_note-feige-2">[2]</a>

The weighted graph bandwidth problem is a <a href="Generalization" title="Generalization">generalization</a> wherein the edges are assigned <a href="Graph_(discrete_mathematics)#Weighted_graph" title="Graph (discrete mathematics)">weights</a> wij and the <a href="Loss_function" title="Loss function">cost function</a> to be minimized is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \max\{\,w_{ij}|f(v_{i})-f(v_{j})|:v_{i}v_{j}\in E\,\}}">

<msub>

</mrow>

</msub>

</mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \max\{\,w_{ij}|f(v_{i})-f(v_{j})|:v_{i}v_{j}\in E\,\}}</annotation>

</semantics>

</math><img src="./f151c481dd4ff8621d359e78387e26ac2a661951.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:35.359ex; height:3.009ex;" alt="{\displaystyle \max\{\,w_{ij}|f(v_{i})-f(v_{j})|:v_{i}v_{j}\in E\,\}}" loading="lazy">.

In terms of matrices, the (unweighted) graph bandwidth is the minimal <a href="Bandwidth_(matrix_theory)" class="mw-redirect" title="Bandwidth (matrix theory)">bandwidth</a> of a <a href="Symmetric_matrix" title="Symmetric matrix">symmetric matrix</a> which is an <a href="Adjacency_matrix" title="Adjacency matrix">adjacency matrix</a> of the graph.

The bandwidth may also be defined as one less than the <a href="Maximum_clique" class="mw-redirect" title="Maximum clique">maximum clique</a> size in a <a href="Proper_interval_graph" class="mw-redirect" title="Proper interval graph">proper interval</a> supergraph of the given graph, chosen to minimize its clique size (<a href="#CITEREFKaplanShamir1996">Kaplan & Shamir 1996</a>).

<div class="mw-heading mw-heading2"><h2 id="Cyclically_interval_graphs">Cyclically interval graphs</h2></div>

For fixed <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"> define for every <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i}</annotation>

</semantics>

</math><img src="./add78d8608ad86e54951b8c8bd6c8d8416533d20.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.802ex; height:2.176ex;" alt="{\displaystyle i}" loading="lazy"> the set

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle I_{k}(i):=[i,i+k+1)}</annotation>

</semantics>

</math><img src="./427e161b1524f196fea0955d7e7dc99931543028.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:20.714ex; height:2.843ex;" alt="{\displaystyle I_{k}(i):=[i,i+k+1)}" loading="lazy">. <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G_{k}(n)}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G_{k}(n)}</annotation>

</semantics>

</math><img src="./61dc12576cf792bd4d9044923546340a276b1f1d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.119ex; height:2.843ex;" alt="{\displaystyle G_{k}(n)}" loading="lazy"> is the corresponding interval graph formed from

the intervals <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle I_{k}(1),I_{k}(2),...I_{k}(n)}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle I_{k}(1),I_{k}(2),...I_{k}(n)}</annotation>

</semantics>

</math><img src="./aa97dbf864868821e64ea2ca120655ded3c83cf3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:20.653ex; height:2.843ex;" alt="{\displaystyle I_{k}(1),I_{k}(2),...I_{k}(n)}" loading="lazy">. These are exactly the proper interval

graphs of graphs having bandwidth <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy">. These graphs are called

cyclically interval graphs because the intervals can be assigned to layers

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle L_{1},L_{2},...L_{k+1}}</annotation>

</semantics>

</math><img src="./4811c2f721264ec08fd67cd00c42926dd89cd595.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:15.216ex; height:2.509ex;" alt="{\displaystyle L_{1},L_{2},...L_{k+1}}" loading="lazy"> in cyclical order, such that the intervals of a layer don't

intersect.

Therefore, one can see the relation to the <a href="Pathwidth" title="Pathwidth">pathwidth</a>. Pathwidth restricted graphs are minor closed but

the set of subgraphs of cyclically interval graphs are not. This follows from the fact that thrinking

degree 2 vertices may increase the bandwidth.

Alternate adding vertices on edges can decrease the bandwidth. This is known as

topologic bandwidth. Another graph measure related through the bandwidth is the

<a href="Bisection_bandwidth" title="Bisection bandwidth">bisection bandwidth</a>.

<div class="mw-heading mw-heading2"><h2 id="Bandwidth_formulas_for_some_graphs">Bandwidth formulas for some graphs</h2></div>

For several families of graphs, the bandwidth <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \varphi (G)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \varphi (G)}</annotation>

</semantics>

</math><img src="./6a8017537912c9982e3941eaf3221b4e7876a3b5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.156ex; height:2.843ex;" alt="{\displaystyle \varphi (G)}" loading="lazy"> is given by an explicit formula.

The bandwidth of a <a href="Path_graph" title="Path graph">path graph</a> Pn on n vertices is 1, and for a complete graph Km we have <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \varphi (K_{n})=n-1}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \varphi (K_{n})=n-1}</annotation>

</semantics>

</math><img src="./29f0ba7cb95ec0a4b58e94cbbae7f8eb774279f9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:15.017ex; height:2.843ex;" alt="{\displaystyle \varphi (K_{n})=n-1}" loading="lazy">. For the <a href="Complete_bipartite_graph" title="Complete bipartite graph">complete bipartite graph</a> Km,n,

<msub>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \varphi (K_{m,n})=\lfloor (m-1)/2\rfloor +n}</annotation>

</semantics>

</math><img src="./709db8a6cf395c4b04e645d11a4342c87971e545.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:27.997ex; height:3.009ex;" alt="{\displaystyle \varphi (K_{m,n})=\lfloor (m-1)/2\rfloor +n}" loading="lazy">, assuming <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m\geq n\geq 1,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m\geq n\geq 1,}</annotation>

</semantics>

</math><img src="./5a0155742a3dd4566dff362626f08277d8aed090.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:11.441ex; height:2.509ex;" alt="{\displaystyle m\geq n\geq 1,}" loading="lazy"></dd></dl>

which was proved by Chvátal.<a href="#cite_note-3">[3]</a> As a special case of this formula, the <a href="Star_graph" class="mw-redirect" title="Star graph">star graph</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S_{k}=K_{k,1}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S_{k}=K_{k,1}}</annotation>

</semantics>

</math><img src="./5b0479f968b1fed94c8ad5ecc4913bc010300186.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:9.953ex; height:2.843ex;" alt="{\displaystyle S_{k}=K_{k,1}}" loading="lazy"> on k + 1 vertices has bandwidth <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \varphi (S_{k})=\lfloor (k-1)/2\rfloor +1}">

<msub>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \varphi (S_{k})=\lfloor (k-1)/2\rfloor +1}</annotation>

</semantics>

</math><img src="./58886799b1712ad23259c3395717d501070e3306.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:24.357ex; height:2.843ex;" alt="{\displaystyle \varphi (S_{k})=\lfloor (k-1)/2\rfloor +1}" loading="lazy">.

For the <a href="Hypercube_graph" title="Hypercube graph">hypercube graph</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Q_{n}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Q_{n}}</annotation>

</semantics>

</math><img src="./503d0af3998f76cd4eaf8b3cc5e8834e254cb71b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.057ex; height:2.509ex;" alt="{\displaystyle Q_{n}}" loading="lazy"> on <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2^{n}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2^{n}}</annotation>

</semantics>

</math><img src="./8226f30650ee4fe4e640c6d2798127e80e9c160d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.381ex; height:2.343ex;" alt="{\displaystyle 2^{n}}" loading="lazy"> vertices the bandwidth was determined by <a href="#CITEREFHarper1966">Harper (1966)</a> to be

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</munderover>

<mrow>

</mrow>

<mrow>

</mrow>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \varphi (Q_{n})=\sum _{m=0}^{n-1}{\binom {m}{\lfloor m/2\rfloor }}.}</annotation>

</semantics>

</math><img src="./9e86a585b98fa1cfd87eeea06d37f5c327bade97.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:23.913ex; height:7.343ex;" alt="{\displaystyle \varphi (Q_{n})=\sum _{m=0}^{n-1}{\binom {m}{\lfloor m/2\rfloor }}.}" loading="lazy"></dd></dl>

Chvatálová showed<a href="#cite_note-4">[4]</a> that the bandwidth of the m × n <a href="Lattice_graph" title="Lattice graph">square grid graph</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P_{m}\times P_{n}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P_{m}\times P_{n}}</annotation>

</semantics>

</math><img src="./a632cdff71f6f2f2aa5e6fbd1cb5ed93a58ee225.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:8.718ex; height:2.509ex;" alt="{\displaystyle P_{m}\times P_{n}}" loading="lazy">, that is, the <a href="Cartesian_product_of_graphs" title="Cartesian product of graphs">Cartesian product</a> of two path graphs on <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m}</annotation>

</semantics>

</math><img src="./0a07d98bb302f3856cbabc47b2b9016692e3f7bc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.04ex; height:1.676ex;" alt="{\displaystyle m}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> vertices, is equal to min{m,n}.

<div class="mw-heading mw-heading2"><h2 id="Bounds">Bounds</h2></div>

The bandwidth of a graph can be bounded in terms of various other graph parameters. For instance, letting χ(G) denote the <a href="Chromatic_number" class="mw-redirect" title="Chromatic number">chromatic number</a> of G,

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \varphi (G)\geq \chi (G)-1;}</annotation>

</semantics>

</math><img src="./5b6d9e020bfbdf9342f5c7470a867325bb963ce3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:17.995ex; height:2.843ex;" alt="{\displaystyle \varphi (G)\geq \chi (G)-1;}" loading="lazy"></dd></dl>

letting diam(G) denote the <a href="Diameter_(graph_theory)" title="Diameter (graph theory)">diameter</a> of G, the following inequalities hold:<a href="#cite_note-5">[5]</a>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \lceil (n-1)/\operatorname {diam} (G)\rceil \leq \varphi (G)\leq n-\operatorname {diam} (G),}</annotation>

</semantics>

</math><img src="./79e40dc1514371b82587c8f38d519248c620c495.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:44.404ex; height:2.843ex;" alt="{\displaystyle \lceil (n-1)/\operatorname {diam} (G)\rceil \leq \varphi (G)\leq n-\operatorname {diam} (G),}" loading="lazy"></dd></dl>

where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> is the number of vertices in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G}</annotation>

</semantics>

</math><img src="./f5f3c8921a3b352de45446a6789b104458c9f90b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.827ex; height:2.176ex;" alt="{\displaystyle G}" loading="lazy">.

If a graph G has bandwidth k, then its <a href="Pathwidth" title="Pathwidth">pathwidth</a> is at most k (<a href="#CITEREFKaplanShamir1996">Kaplan & Shamir 1996</a>), and its <a href="Tree-depth" title="Tree-depth">tree-depth</a> is at most k log(n/k) (<a href="#CITEREFGruber2012">Gruber 2012</a>). In contrast, as noted in the previous section, the star graph Sk, a structurally very simple example of a <a href="Tree_(graph_theory)" title="Tree (graph theory)">tree</a>, has comparatively large bandwidth. Observe that the <a href="Pathwidth" title="Pathwidth">pathwidth</a> of Sk is 1, and its tree-depth is 2.

Some graph families of bounded degree have sublinear bandwidth: <a href="#CITEREFChung1988">Chung (1988)</a> proved that if T is a tree of maximum degree at most ∆, then

<mfrac>

<mrow>

</mrow>

<mrow>

<msub>

</mrow>

</msub>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \varphi (T)\leq {\frac {5n}{\log _{\Delta }n}}.}</annotation>

</semantics>

</math><img src="./b2ef24fd8fd48a35a486217be3967a3cfa1f6653.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:15.902ex; height:5.843ex;" alt="{\displaystyle \varphi (T)\leq {\frac {5n}{\log _{\Delta }n}}.}" loading="lazy"></dd></dl>

More generally, for <a href="Planar_graph" title="Planar graph">planar graphs</a> of bounded maximum degree at most ∆, a similar bound holds (cf. <a href="#CITEREFBöttcherPruessmannTarazWürfl2010">Böttcher et al. 2010</a>):

<mfrac>

<mrow>

</mrow>

<mrow>

<msub>

</mrow>

</msub>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \varphi (G)\leq {\frac {20n}{\log _{\Delta }n}}.}</annotation>

</semantics>

</math><img src="./7ea22972d257e5b5ea63b9f5bc54f7f7648e82e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:16.092ex; height:5.843ex;" alt="{\displaystyle \varphi (G)\leq {\frac {20n}{\log _{\Delta }n}}.}" loading="lazy"></dd></dl>

<div class="mw-heading mw-heading2"><h2 id="Computing_the_bandwidth">Computing the bandwidth</h2></div>

Both the unweighted and weighted versions are special cases of the <a href="Quadratic_bottleneck_assignment_problem" title="Quadratic bottleneck assignment problem">quadratic bottleneck assignment problem</a>.

The bandwidth problem is <a href="NP-hard" class="mw-redirect" title="NP-hard">NP-hard</a>, even for some special cases.<a href="#cite_note-6">[6]</a> Regarding the existence of efficient

<a href="Approximation_algorithm" title="Approximation algorithm">approximation algorithms</a>, it is known that the bandwidth is <a href="Hardness_of_approximation" title="Hardness of approximation">NP-hard to approximate</a> within any constant, and this even holds when the input graphs are restricted to <a href="Caterpillar_tree" title="Caterpillar tree">caterpillar trees</a> with maximum hair length 2 (<a href="#CITEREFDubeyFeigeUnger2010">Dubey, Feige & Unger 2010</a>).

For the case of dense graphs, a 3-approximation algorithm was designed by <a href="#CITEREFKarpinskiWirtgenZelikovsky1997">Karpinski, Wirtgen & Zelikovsky (1997)</a>.

On the other hand, a number of polynomially-solvable special cases are known.<a href="#cite_note-feige-2">[2]</a> A <a href="Heuristic" title="Heuristic">heuristic</a> algorithm for obtaining linear graph layouts of low bandwidth is the <a href="Cuthill%E2%80%93McKee_algorithm" title="Cuthill–McKee algorithm">Cuthill–McKee algorithm</a>. Fast multilevel algorithm for graph bandwidth computation was proposed in.<a href="#cite_note-multilevellinord-7">[7]</a>

<div class="mw-heading mw-heading2"><h2 id="Applications">Applications</h2></div>

The interest in this problem comes from some application areas.

One area is <a href="Sparse_matrix" title="Sparse matrix">sparse matrix</a>/<a href="Band_matrix" title="Band matrix">band matrix</a> handling, and general algorithms from this area, such as <a href="Cuthill%E2%80%93McKee_algorithm" title="Cuthill–McKee algorithm">Cuthill–McKee algorithm</a>, may be applied to find approximate solutions for the graph bandwidth problem.

Another application domain is in <a href="Electronic_design_automation" title="Electronic design automation">electronic design automation</a>. In <a href="Standard_cell" title="Standard cell">standard cell</a> design methodology, typically standard cells have the same height, and their <a href="Placement_(EDA)" class="mw-redirect" title="Placement (EDA)">placement</a> is arranged in a number of rows. In this context, graph bandwidth problem models the problem of placement of a set of standard cells in a single row with the goal of minimizing the maximal <a href="Propagation_delay" title="Propagation delay">propagation delay</a> (which is assumed to be proportional to wire length).

<ul><li><a href="Cutwidth" title="Cutwidth">Cutwidth</a> and <a href="Pathwidth" title="Pathwidth">pathwidth</a>, different NP-complete optimization problems involving linear layouts of graphs.</li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

<li id="cite_note-1"><a href="#cite_ref-1">^</a> (<a href="#CITEREFChinnChvátalováDewdneyGibbs1982">Chinn et al. 1982</a>)

</li>

<li id="cite_note-feige-2">^ <a href="#cite_ref-feige_2-0">a</a> <a href="#cite_ref-feige_2-1">b</a> "Coping with the NP-Hardness of the Graph Bandwidth Problem", Uriel Feige, <a href="Lecture_Notes_in_Computer_Science" title="Lecture Notes in Computer Science">Lecture Notes in Computer Science</a>, Volume 1851, 2000, pp. 129-145, <style data-mw-deduplicate="TemplateStyles:r1238218222">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F3-540-44985-X_2">10.1007/3-540-44985-X_2</a>

</li>

<li id="cite_note-3"><a href="#cite_ref-3">^</a> A remark on a problem of Harary. V. Chvátal, Czechoslovak Mathematical Journal 20(1):109–111, 1970. <a rel="nofollow" class="external text" href="http://dml.cz/dmlcz/100949">http://dml.cz/dmlcz/100949</a>

</li>

<li id="cite_note-4"><a href="#cite_ref-4">^</a> Optimal Labelling of a product of two paths. J. Chvatálová, Discrete Mathematics 11, 249–253, 1975.

</li>

<li id="cite_note-5"><a href="#cite_ref-5">^</a> <a href="#CITEREFChinnChvátalováDewdneyGibbs1982">Chinn et al. 1982</a>

</li>

<li id="cite_note-6"><a href="#cite_ref-6">^</a> Garey–Johnson: GT40

</li>

<cite id="CITEREFIlya_Safro_and_Dorit_Ron_and_Achi_Brandt2008" class="citation journal cs1">Ilya Safro and Dorit Ron and Achi Brandt (2008). "Multilevel Algorithms for Linear Ordering Problems". ACM Journal of Experimental Algorithmics. 13: 1.4 – 1.20. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F1412228.1412232">10.1145/1412228.1412232</a>.</cite>

</li>

</ol></div></div>

<ul><li><cite id="CITEREFBöttcherPruessmannTarazWürfl2010" class="citation journal cs1">Böttcher, J.; Pruessmann, K. P.; Taraz, A.; Würfl, A. (2010). "Bandwidth, expansion, treewidth, separators and universality for bounded-degree graphs". European Journal of Combinatorics. 31 (5): 1217–1227. <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/0910.3014">0910.3014</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.ejc.2009.10.010">10.1016/j.ejc.2009.10.010</a>.</cite></li>

<li><cite id="CITEREFChinnChvátalováDewdneyGibbs1982" class="citation journal cs1"><a href="Phyllis_Chinn" title="Phyllis Chinn">Chinn, P. Z.</a>; Chvátalová, J.; <a href="Alexander_Dewdney" class="mw-redirect" title="Alexander Dewdney">Dewdney, A. K.</a>; Gibbs, N. E. (1982). "The bandwidth problem for graphs and matrices—a survey". Journal of Graph Theory. 6 (3): 223–254. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1002%2Fjgt.3190060302">10.1002/jgt.3190060302</a>.</cite></li>

<li><cite id="CITEREFChung1988" class="citation cs2"><a href="Fan_Chung" title="Fan Chung">Chung, Fan R. K.</a> (1988), "Labelings of Graphs", in Beineke, Lowell W.; Wilson, Robin J. (eds.), <a rel="nofollow" class="external text" href="http://www.math.ucsd.edu/~fan/mypaps/fanpap/86log.PDF">Selected Topics in Graph Theory</a> (PDF), Academic Press, pp. 151–168, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-12-086203-0</bdi></cite></li>

<li><cite id="CITEREFDubeyFeigeUnger2010" class="citation journal cs1">Dubey, C.; Feige, U.; Unger, W. (2010). <a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.jcss.2010.06.006">"Hardness results for approximating the bandwidth"</a>. Journal of Computer and System Sciences. 77: 62–90. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.jcss.2010.06.006">10.1016/j.jcss.2010.06.006</a>.</cite></li>

<li><cite id="CITEREFGareyJohnson,_D.S.1979" class="citation book cs1"><a href="Michael_Garey" title="Michael Garey">Garey, M.R.</a>; <a href="David_S._Johnson" title="David S. Johnson">Johnson, D.S.</a> (1979). <a href="Computers_and_Intractability%3A_A_Guide_to_the_Theory_of_NP-Completeness" class="mw-redirect" title="Computers and Intractability: A Guide to the Theory of NP-Completeness">Computers and Intractability: A Guide to the Theory of NP-Completeness</a>. New York: W.H. Freeman. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-7167-1045-5</bdi>.</cite></li>

<li><cite id="CITEREFGruber2012" class="citation cs2">Gruber, Hermann (2012), "On Balanced Separators, Treewidth, and Cycle Rank", Journal of Combinatorics, 3 (4): 669–682, <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/1012.1344">1012.1344</a>, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.4310%2Fjoc.2012.v3.n4.a5">10.4310/joc.2012.v3.n4.a5</a></cite></li>

<li><cite id="CITEREFHarper1966" class="citation journal cs1">Harper, L. (1966). <a rel="nofollow" class="external text" href="https://doi.org/10.1016%2FS0021-9800%2866%2980059-5">"Optimal numberings and isoperimetric problems on graphs"</a>. Journal of Combinatorial Theory. 1 (3): 385–393. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2FS0021-9800%2866%2980059-5">10.1016/S0021-9800(66)80059-5</a>.</cite></li>

<li><cite id="CITEREFKaplanShamir1996" class="citation cs2">Kaplan, Haim; Shamir, Ron (1996), "Pathwidth, bandwidth, and completion problems to proper interval graphs with small cliques", <a href="SIAM_Journal_on_Computing" title="SIAM Journal on Computing">SIAM Journal on Computing</a>, 25 (3): 540–561, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1137%2Fs0097539793258143">10.1137/s0097539793258143</a></cite></li>

<li><cite id="CITEREFKarpinskiWirtgenZelikovsky1997" class="citation journal cs1">Karpinski, Marek; Wirtgen, Jürgen; Zelikovsky, Aleksandr (1997). <a rel="nofollow" class="external text" href="http://eccc.hpi-web.de/report/1997/017/">"An Approximation Algorithm for the Bandwidth Problem on Dense Graphs"</a>. Electronic Colloquium on Computational Complexity. 4 (17).</cite></li></ul>

<div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2></div>

<ul><li><a rel="nofollow" class="external text" href="http://www.csc.kth.se/~viggo/wwwcompendium/node53.html">Minimum bandwidth problem</a>, in: Pierluigi Crescenzi and Viggo Kann (eds.), A compendium of NP optimization problems. Accessed May 26, 2010.</li></ul></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-07-02" href="https://en.wikipedia.org/wiki/?title=Graph_bandwidth&oldid=1298467075">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>